package Elementary_algorithm.String;


import org.junit.Test;

/*
「外观数列」是一个数位字符串序列，由递归公式定义：

countAndSay(1) = "1"
countAndSay(n) 是countAndSay(n-1) 的行程长度编码。
行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。
例如，要压缩字符串"3322251"，我们将"33"用"23"替换，将"222"用"32"替换，将"5"用"15"替换并将"1"用"11"替换。
因此压缩后字符串变为 "23321511"。

给定一个整数n，返回外观数列的第n个元素。

示例 1：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"

countAndSay(2) = "1" 的行程长度编码 = "11"

countAndSay(3) = "11" 的行程长度编码 = "21"

countAndSay(4) = "21" 的行程长度编码 = "1211"

示例 2：
输入：n = 1
输出："1"
解释：

这是基本情况。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnpvdm/
 */
public class _07外观数列 {

    @Test
    public void test() {

    }

    /*
    官解一：遍历生成
    //通过阅读题目，我们可以了解到所谓的「外观数列」，其实本质上只是依次统计字符串中连续相同字符的个数。
    //然后一直拼接知道for循环结束
    链接：https://leetcode.cn/problems/count-and-say/solutions/1047325/wai-guan-shu-lie-by-leetcode-solution-9rt8/
     */

    class Solution {
        public String countAndSay(int n) {
            String str = "1";
            for (int i = 2; i <= n; ++i) {
                StringBuilder sb = new StringBuilder();
                int start = 0;
                int pos = 0;
                //依次统计字符串中连续相同字符的个数。
                //pos是连续相同字符的个数
                //start是当前字母的指针
                while (pos < str.length()) {
                    while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                        pos++;
                    }
                    //pos - start 是所有情况中连续相同字符个数的通式
                    sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                    start = pos;
                }
                str = sb.toString();
            }

            return str;
        }
    }
}
